import java.util.HashMap;
import java.util.Map;

public class MaxSubArray {

	public static Map<String, Integer> maxSubArray(int low, int high, Integer[] arr) {
		Map<String, Integer> map = new HashMap<String, Integer>();
		Map<String, Integer> retMap = new HashMap<String, Integer>(); // 返回值
		if (low == high) {
			map.put("low", low);
			map.put("high", high);
			map.put("max", arr[low]);
			return map;
		}
		int mid = (low + high) / 2;
		Map<String, Integer> left = maxSubArray(low, mid, arr);
		Map<String, Integer> right = maxSubArray(mid+1, high, arr);
		Map<String, Integer> midMap = maxCrossSubArray(low, mid, high, arr);
		
		if (left.get("max") >= right.get("max") && left.get("max") >= midMap.get("max")) {
			retMap.put("low", left.get("low"));
			retMap.put("high", left.get("high"));
			retMap.put("max", left.get("max"));
		} else if (right.get("max") >= left.get("max") && right.get("max") >= midMap.get("max")) {
			retMap.put("low", right.get("low"));
			retMap.put("high", right.get("high"));
			retMap.put("max", right.get("max"));
		} else {
			retMap.put("low", midMap.get("low"));
			retMap.put("high", midMap.get("high"));
			retMap.put("max", midMap.get("max"));
		}
		return retMap;
	}
	
	public static Map<String, Integer> maxCrossSubArray(int low, int mid, int high, Integer[] arr) {
		Map<String, Integer> map = new HashMap<String, Integer>();
		int leftSum = -65535, rightSum = -65535, sum = 0;
		int leftIdx = 0, rightIdx = 0;
		for (int i = mid; i >= low; i--) {
			sum = sum + arr[i];
			if (sum > leftSum) {
				leftSum = sum;
				leftIdx = i;
			}
		}
		sum = 0;
		for (int j = mid+1; j <= high; j++) {
			sum = sum + arr[j];
			if (sum > leftSum) {
				rightSum = sum;
				rightIdx = j;
			}
		}
		map.put("low", leftIdx);
		map.put("high", rightIdx);
		map.put("max", leftSum + rightSum);
		return map;
	}

	public static void main(String[] args) {
		Integer[] arr = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
		Map<String, Integer> map = MaxSubArray.maxSubArray(0, arr.length-1, arr);
		System.out.printf("最大子数组包含的元素从索引%d到%d，值为%d", map.get("low"), map.get("high"), map.get("max"));
	}
}
